'''一些最基础的数值转换题'''
from typing import List
from collections import Counter
# 1. 进制转换
# while True:
#     try:
#         print(int(input(), 16)) #输入一个16进制的数字
#     except:
#         break
#   1.1 16进制转换2进制
print(bin(int('f', 16)))  # 注意格式,int(str, 16)是要输入字符串，不是直接给数字, 把16进制的str变成10进制
#   1.2 转换8进制
print(oct(0xf))  # 任何进制都可直接使用8进制转换
print(oct(int('f', 16))) # f = 15  # 把16进制的字符串变成10进制再变成8进制
#   1.3 转换16进制
print(hex(int('17', 8))) # 8**1 + 7 = 15
print('---------------------------------------')
#----------------------------------------------

# 2. 明明的随机数，去除重复数字并排序
class Solution:
    def randnum(self, nums:List[int]) -> List[int]:
        temp =set()
        for i in range(len(nums)):
            temp.add(nums[i])
        return list(sorted(temp))
# nums = [1,1,20,3,2,5,6,7,3,5,4,8,5,1,2]
# s = Solution()
# print(s.randnum(nums))
print('---------------------------------------')
#----------------------------------------------

# 3. 字符个数统计
class Solution02:
    def countchar(self, str_in:str) -> int:
        res =set()
        for i in range(len(str_in)):
            res.add(str_in[i])
        return len(res)

# str_in = 'asfsddfaw'
# s = Solution02()
# print(s.countchar(str_in))
print('---------------------------------------')
#----------------------------------------------



'''
# 4. NC68 跳台阶
# 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）
# 方法三： 动态规划
动态规划思想：
如果这只青蛙，跳上了第n级台阶，那么最后一次跳跃之前，他一定在n-1级台阶或n-2级台阶上。
那么跳上n级台阶有多少种情況就变成了两个子问题:
跳上n-1级台阶的跳法 + 跳上n-2级台阶的跳法
按照此逻辑递推:
跳上n-1级台阶可以拆解为两个子问题：
即：跳上n-2级台阶的跳法 + 跳上n-3级台阶的跳法
f ( n ) = f ( n - 1 ) + f ( n - 2 )
————————————————
原文链接：https://blog.csdn.net/weixin_45463061/article/details/126581128
'''
class Solution03:
    def jumpFloor(self, number: int) -> int:
        if number < 3:
            return number
        a, b = 1, 2
        for item in range(3, number):
            '''
            为什么a = b?
            因为a为n-2，下一次递归时，a就变成了n-1，
            而之前，b就在n-1的位置，所以把b的值转让给了a
            '''
            a, b = b, a+b #a 代表n-2级台阶，b代表n-1级台阶
        return a+b # 最后返回第n级台阶

# num_floor = 5
# s =Solution03()
# print(s.jumpFloor(num_floor))
print('---------------------------------------')
#----------------------------------------------


''' 5. 坐标移动
数据范围：每组输入的字符串长度满足 1≤n≤10000 ，坐标保证满足 -2^31≤x, y≤2^31 -1，且数字部分仅含正数
开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动
    输入：
        A10;S20;W10;D30;X;A1A;B10A11;;A10;
    输出：
        10,-10
'''
class Solution04:
    def coordinate(self, string: str):
        if 1 <= len(string) <= 10000:
            v = [0, 0]
            alist = string.split(";")
            for item in alist:
                if len(item) <= 3 and item[1:].isdigit(): # .isdigit()判断是否为数字字符串
                    if item.startswith('A'):
                        v[0] -= int(item[1:])
                        # continue
                    elif item.startswith("D"):
                        v[0] += int(item[1:])
                        # continue
                    elif item.startswith("W"):
                        v[-1] += int(item[1:])
                        # continue
                    elif item.startswith("S"):
                        v[-1] -= int(item[1:])
                        # continue
            if -2**31 <= v[0] and v[0] <= 2**31 - 1 and v[-1] <= 2**31 - 1 and -2**31 <= v[-1]:
                return v[0], v[-1]

# s = Solution04()
# a, b = s.coordinate(input(""))
# print("{0},{1}".format(a, b))
print('---------------------------------------')
#----------------------------------------------

''' 6. 验证码
密码要求:
1.长度超过8位
2.包括大小写字母.数字.其它符号,以上四种至少三种
3.不能有长度大于2的包含公共元素的子串重复 （注：其他符号不含空格或换行）
数据范围：输入的字符串长度满足 1≤n≤100
'''
def check(s):
    if len(s)>100 or len(s)<8 or ' ' in s or '\n' in s:#判断长度是否符合要求,以及是否存在空格和换行
        return 'NG'
    a,b,c,d=0,0,0,0#a,b,c,d分别代表一种符号
    # lenth = len(s)
    for item in s:#遍历字符串，用ascall吗来查看是否有某种类型符号
        if ord('a')<=ord(item)<=ord('z'):
            a=1
        elif ord('A')<=ord(item)<=ord("Z"):
            b=1
        elif ord('0')<=ord(item)<=ord("9"):
            c=1
        else:
            d=1
    if a+b+c+d<3:#判断是否符合字符种类至少有三种的要求
        return 'NG'
    for i in range(len(s)-3):#将字符串按分片的字符串分开，一般情况下只能分成两份，即一刀两段，如果有三段，则证明有长度大于2的包含公共元素的子串重复
        if len(s.split(s[i:i+3]))>=3:
            return 'NG'
    return 'OK'

# while True:
#     try:
#         res = check(input())
#         print(res)
#     except:
#         break
#----------------------------------------------


''' 7. HJ23.删除字符串中出现次数最少的字符 
'''
class Solution06:
    def deletemin(self, s: str) -> str:
        s_dict = {}
        res = s
        for i in s:
            if not (i in s_dict):
                s_dict[i] = 1
                # print(i)
            else:
                s_dict[i] += 1
                # print(s_dict[i])
        s_dict_list = list(sorted(s_dict.items(), key=lambda x:x[1]))
        min_value = s_dict_list[0][1]
        for item in s_dict_list:
            if item[1] == min_value:
                min_item = item[0]
                res = res.replace(min_item, '')
                print(min_item)
        return res

    def deletemin02(s: str) -> str:
        res = s
        char_list = Counter(s) # 统计
        char_list = sorted(char_list.items(), key=lambda x: x[1]) # 排序
        min_value = char_list[0][1]
        # print(char_list)
        for i in char_list:
            if i[1] == min_value:
                res = res.replace(i[0], '') # 删除
            else:
                break
        return res
# str06 = 'aabcdddzz54324'
# s = Solution06()
# print(s.deletemin(str06))
#----------------------------------------------

# 8. IP地址与整数的互换
class Solution07:
    def transf_ip_num(self,ip:str, num:str) ->str:
        # ip地址一共4段，每一段由8位二进制组成
        """
        如果输入的是一个ip地址，首先将字符串以.为分隔符分开，再对每一块进行
        二进制转换，十进制或者其他进制转二进制时，前面会加上两个字符的前缀
        所以需要切片，然后对二进制数补0，将字符串拼起来，然后转化为10进制
        """
        list1 = ip.split('.')
        target = str()
        for i in list1:
            a = bin(int(i, 10))[2:] # 二进制的字符串开头含有0b两个字符
            # print(type(a)) # 二进制数 类型为 字符串
            if len(a) < 8:
                s = '0' * (8 - len(a)) + a
            else:
                s = a
            target += s
        # print(int(target, 2)) # 转换为10进制

        """
        如果输入的是整数，先将其转化为2进制，记得分片，然后补0，
        再用循环分片将其分为8个一组，对每组进行转化整数，然后变成字符串，
        加入数组，用.将数组中的元素链接，形成ip地址
        """
        res = []
        num2 = bin(int(num, 10))[2:]
        print(num2)
        num2 = '0' * (32 - len(num2)) + num2 if len(num2) < 32 else num2
        print(num2)

        for i in range(4):
            b = num2[8 * i:8 * i + 8]
            b = str(int(b, 2))
            res.append(b)
        # print('.'.join(res))
        return int(target, 2), '.'.join(res)

# ip = '10.0.3.193'
# nums = '167969729'
# s = Solution07()
# newnum, newip = s.transf_ip_num(ip,nums)
# print(newnum)
# print(newip)
# print(int('0b11000001', 2))
#--------------------------------------------------------


''' 9. HJ101.输入整型数组和排序标识
描述
输入整型数组和排序标识，对其元素按照升序或降序进行排序
数据范围： 1 <= n <= 1000，元素大小满足 0 <= val <= 100000
输入描述：
第一行输入数组元素个数
第二行输入待排序的数组，每个数用空格隔开
第三行输入一个整数0或1。0代表升序排序，1代表降序排序
原文链接：https://blog.csdn.net/SuperMiraak/article/details/124972565
    输入：
    8
    1 2 4 9 3 55 64 25
    0
    输出：
    1 2 3 4 9 25 55 64
'''
class Solution08:
    def sortnums(self):
        input('输入数组元素个数：\n')
        listnums = list(map(int, input('输入待排序的数组，每个数用空格隔开: \n').split(' ')))
        # print(listnums)
        temp =[]
        res = []
        mode = input('输入一个整数0或1。0代表升序排序，1代表降序排序:\n')
        if mode == '0':
            temp = sorted(listnums)
        elif mode == '1':
            temp = sorted(listnums, reverse=True)
        for i in temp:
            res.append(str(i))
        return ' '.join(res)

# s = Solution08()
# sorted_nums = s.sortnums()
# print(sorted_nums)
#--------------------------------------------------------


# 10. 字符串逆序
def rev_str(s_input):
    return s_input[::-1]

# s = 'I am a student'
# print(rev_str(s))
#--------------------------------------------------------



''' # 11. NC52 有效括号序列 
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
'''
class Solution09:
    def isValid(self , s: str) -> bool:
        dic={"}":"{",")":"(","]":"["} # 用括号末端对比前半括号
        half=[]
        for v in s:
            if v in '{([':
                half.append(v)
            elif v in ']})':
                # half[-1] 即 上一次遇见的半括号，
                # dic[v]==half[-1] 即 判断前一个括号类型是否是当前遇见的括号相匹配
                if len(half)>0 and dic[v]==half[-1]:
                    # 为应对多括号情况，遇见匹配的括号就删去当前匹配好的括号
                    # 比如{[()]}，先删去(),再[]，最后{}
                    half.pop()
                else:
                    return False
        return len(half)==0 # 当字符串中括号全都匹配正确了，就返回True
# str1 = '['
# s = Solution09()
# print(s.isValid(str1))

'''     12. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，
那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列

两种特殊情况：
① 空列表
② 列表全是递增
'''
from typing import List
class Solution10:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        num_count = 1
        ans = 1
        for index in range(1,len(nums)):
            if nums[index] > nums[index-1]:
                # print(num_count)
                num_count += 1
            else: # 发现不递增，就重头计数
                # 数组里全是递增数时不执行
                ans = max(num_count, ans)
                num_count = 1
            ans = max(num_count, ans)  # 防止数组里全是递增数字
        return ans

# input001 = [1,3,5,7]
# s =Solution10()
# print(s.findLengthOfLCIS(input001))









